package com.algorithm.string;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: LK
 * Date: 2018/5/22
 * Time: 14:26
 * To change this template use File | Settings | File Templates.
 * Description:
 *  输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 *  例如输入字符串abc,则打印出由字符a,b,c
 *  所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
 *  输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母
 */
public class StringToArray {

        private ArrayList<String> ret = new ArrayList<>();

        public ArrayList<String> Permutation(String str) {
            if (str.length() == 0)
                return ret;
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            backtracking(chars, new boolean[chars.length], new StringBuffer());
            return ret;
        }

        private void backtracking(char[] chars, boolean[] hasUsed, StringBuffer s) {
            if (s.length() == chars.length) {
                ret.add(s.toString());
                return;
            }
            for (int i = 0; i < chars.length; i++) {
                if (hasUsed[i])
                    continue;
                if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1])
                    continue; // 保证不重复
                hasUsed[i] = true;
                s.append(chars[i]);
                backtracking(chars, hasUsed, s);
                s.deleteCharAt(s.length() - 1);
                hasUsed[i] = false;
            }
        }

        public static void main(String[] args) {
            String str="abc";
            StringToArray ts = new StringToArray();
            ArrayList<String> permutation = ts.Permutation(str);
            System.out.println(permutation);
        }



}
